对于二值图像的连通域标记算法，常见的使用方法是opencv里的connectedComponents()以及connectedComponentsWithStats()，这个实现方法很快，使用也便捷，但无法适用于3D图像。skimage中的skimage.measure.label()以及skimage.measure.regionprops()可以得到2D和3D图像的连通域和相关的统计信息，但这个实现方法较慢，对于尺寸大的3D图像（比如512*512*512尺寸的医学影像）并非最优解。

这里简单介绍一个提速的2D/3D图像连通域标记的Python/C++开源包：connected-components-3d(link)。这个包的实现结合了two-pass算法，Array-Based Union-Find并查集来存储label信息，对于3D图像的处理更快，还能够直接处理非二值图像，下载方便，使用方法简单，强烈推荐～

Python版本直接pip install下载，C++版本可以去github(link)上下载源码。

使用：

详情请直接去github上并支持原作者:)

我们先用较为简单直观的2D图像来做示例，再扩展到3D图像。这里举例的是8邻域的连通域。主要思路是Two Pass算法，这个算法包括两次扫描，大体过程是这样的：

这个算法的实现中有可以提速的点：

相邻关系的记录使用Union-Find并查集，也能适用于非二值图，可以用一个array来实现。

在第一遍扫描的时候，对于前景像素的判断，需要对于其周围的8个像素都遍历取值，这个过程是比较慢的。我们是从上到下、从左到右扫描的，有些点的状态是已知的，经过对于拓扑关系的总结，我们可以只用8邻域中左上角的4个点来对当前前景点做出判断。这个判断关系可以用决策树来表示，并通过优化决策树结构（判断步骤最少），可以得到对于一个前景点标记的最终判断条件。

值得一提的是，对于2D的情况，可以对于多个像素合成block，以block为单位来一次性判断和赋值多个像素点来提高速度（Blocked Based Decision Tree）。 PS. 这个方法在2D图像的情况下很快，但目前还未有很好的3D图像版本的实现。

我们可以想象，把之前的2D图像扩展成3D，这里以26邻域连通域举例。我们的步骤是一样的，仍旧是Two Pass，但在第一次扫描时，判断每个前景像素点的时间更久了，因为周围有26个点需要取值来进行判断。我们用之前相同的优化逻辑，同样利用拓扑和优化决策树找到最优的判断条件。如果要看详细的具体判断条件可以直接看论文或者看代码。

这个包的作者还添加了一些代码实现上的加速：